// 边  表结点声明
typedef struct EdgeNode	
{
	int adjvex;					// 邻接点域，存储该顶点对应的下标				
	struct EdgeNode *next;		// 链域，指向下一个邻接点
}EdgeNode;

// 顶点 表结点声明
typedef struct VertexNode
{
	int in;						// 顶点入度
	int data;					// 顶点域，存储顶点信息
	EdgeNode *firstedge;		// 边表头指针
}VertexNode, AdjList[MAXVEX];	

typedef struct
{
	AdjList adjList;				//adjList为指向邻接表的指针
	int numVertexes, numEdges;		//图中当前顶点数和边数
}graphAdjList, *GraphAdjList;		//声明图的邻接表

int *etv, *ltv;
int *stack2;			// 用于存储拓扑序列的栈
int top2;				// 用于stack2的栈顶指针

// 拓扑排序算法
// 若GL无回路，则输出拓扑排序序列并返回OK，否则返回ERROR
Status TopologicalSort(GraphAdjList GL)
{
	EdgeNode *e;
	int i, k, gettop;
	int top = 0;		// 用于栈指针下标索引
	int count = 0;		// 用于统计输出顶点的个数
	int *stack;			// 用于存储入度为0的顶点
	
	stack = (int *)malloc(GL->numVertexes * sizeof(int));
	
	for( i=0; i < GL->numVertexes; i++ )
	{
		if( 0 == GL->adjList[i].in )		//邻接表第i个顶点的入度为0
		{
			stack[++top] = i;	// 将度为0的顶点下标入栈
		}
	}
	
	// 初始化etv都为0,顶点最早发生时间
	top2 = 0;
	etv = (int *)malloc(GL->numVertexes*sizeof(int));
	for( i=0; i < GL->numVertexes; i++ )
	{
		etv[i] = 0;
	}
	stack2 = (int *)malloc(GL->numVertexes*sizeof(int));
	
	while( 0 != top )				//当top非0即stack栈非空
	{
		gettop = stack[top--];		// 出栈，gettop=度为0的顶点下标
		// printf("%d -> ", GL->adjList[gettop].data); 
		stack2[++top2] = gettop;	// 保存拓扑序列顺序 C1 C2 C3 C4 .... C9
		count++;				
		
		for( e=GL->adjList[gettop].firstedge; e; e=e->next )	//遍历下标为gettop的顶点的边，只要e不为null就一直循环，拓补排序
		{
			k = e->adjvex;			//k用来保存下一个顶点的下标
			
			// 注意：下边这个if条件是分析整个程序的要点！
			// 将k号顶点邻接点的入度-1，因为他的前驱已经消除
			// 接着判断-1后入度是否为0，如果为0则也入栈
			if( !(--GL->adjList[k].in) )	
			{
				stack[++top] = k;
			}
			
			if( (etv[gettop]+e->weight) > etv[k] )		//如果当前结点的etv+边的权值＞下一个结点的etv
			{
				etv[k] = etv[gettop] + e->weight;		//下一个结点的etv取大
			}
		}
	}
	
	if( count < GL->numVertexes )	// 如果count小于顶点数，说明存在环
	{
		return ERROR;
	}
	else
	{
		return OK;
	}
}

// 求关键路径，GL为有向图，输出GL的各项关键活动
void CriticalPath(GraphAdjList GL)
{
	EdgeNode *e;
	int i, gettop, k, j;
	int ete, lte;
	
	// 调用改进后的拓扑排序，求出etv和stack2的值
	TopologicalSort(GL);
	
	// 初始化ltv都为汇点的时间
	ltv = (int *)malloc(GL->numVertexes*sizeof(int));
	for( i=0; i < GL->numVertexes; i++ )
	{
		ltv[i] = etv[GL->numVertexes-1];		
	}
	
	// 从汇点倒过来逐个计算ltv
	while( 0 != top2 )
	{
		gettop = stack2[top2--];									// 注意，第一个出栈是汇点，stack2[]保存拓扑序列
		for( e=GL->adjList[gettop].firstedge; e; e=e->next )
		{
			k = e->adjvex;											//k用来保存下一个顶点的下标
			if( (ltv[k] - e->weight) < ltv[gettop] )				//如果下一个结点的ltv-边的权值<当前结点的ltv
			{
				ltv[gettop] = ltv[k] - e->weight;					//当前结点的ltv取小
			}
		}
	}
	
	// 通过etv和ltv求ete和lte
	for( j=0; j < GL->numVertexes; j++ )
	{
		for( e=GL->adjList[j].firstedge; e; e=e->next )				//遍历j顶点的所有邻接点
		{
			k = e->adjvex;											//k用来保存下一个顶点的下标
			ete = etv[j];
			lte = ltv[k] - e->weight;			
			
			if( ete == lte )					//相等时，活动为关键活动，关键活动组成的路径就是关键路径
			{
				printf("<v%d,v%d> length: %d , ", GL->adjList[j].data, GL->adjList[k].data, e->weight );
			}
		}
	}
}